#include "cfg.h"


// this function checks if multiple loops have the same header.
int check_for_same_header(instr_node * preheaders, simple_instr * preheader) {
	instr_node * current_instr = preheaders;

	while(current_instr) {
		if(current_instr->instr == preheader) {
			return TRUE;
		}
		current_instr = current_instr->next;
	}

	return FALSE;
}

/***
	finds backedges and modifies the instruction list accordingly. 
***/
void find_loops(basic_block_node * cfg, simple_instr **inlist, instr_node ** preheaders) {
	basic_block_node * current_block = NULL;
	block_ptr * current_successor = NULL;
	instr_node * lastinstr = NULL;
	int preheader_count = 0;
	
	for(current_block = cfg; current_block; current_block = current_block->next) {
		for(current_successor = current_block->successor; current_successor; current_successor = current_successor->next) {
			if(get_bit(current_block->dom, current_successor->block->number)) {
				basic_block_node * successor_block = current_successor->block;
				simple_instr * insert_instr = NULL;
				instr_node * newinstr = NULL;
				block_ptr * predecessor_block = NULL;
				simple_instr * temp = NULL;

				if(check_for_same_header(*preheaders, successor_block->start->instr->prev))
					continue;

               // printf("\n\t\t\t\tfound backedge %d\n", current_block->number);

                temp = current_block->previous /* && get_bit(current_block->previous->dom, current_successor->block->number) */ ? current_block->previous->end->instr : NULL;
/*
				if(temp && simple_op_format(temp->opcode) != BJ_FORM && simple_op_format(temp->opcode) != MBR_FORM)
				{
					simple_instr * newjmp = new_instr(JMP_OP, simple_type_void);
					newjmp->u.bj.target = current_block->start->instr->u.label.lab;

					newjmp->next = temp->next;
					newjmp->prev = temp;
					temp->next->prev = newjmp;
					temp->next = newjmp;
				//	printf("\n\nHIDDEN LOOP DETECTED current_block->number = %d  successor_block->number = %d\n\n", current_block->number, current_successor->block->number);
                    continue;
				}
*/
				insert_instr = new_instr(LABEL_OP, simple_type_void);
				insert_instr->u.label.lab = new_label();

				if(successor_block->start->instr->prev == NULL) {
					insert_instr->next = *inlist;
					insert_instr->prev = NULL;
					*inlist = insert_instr;
				} else {
					insert_instr->next = successor_block->start->instr;
					insert_instr->prev = successor_block->start->instr->prev;
					successor_block->start->instr->prev->next = insert_instr;
					successor_block->start->instr->prev = insert_instr;
				}

				newinstr = (instr_node *) malloc(sizeof(instr_node));
				newinstr->previous = lastinstr;
				newinstr->instr = insert_instr;
				newinstr->next = NULL;
				if(*preheaders == NULL)
					*preheaders = newinstr;
				else
					lastinstr->next = newinstr;
			
				lastinstr = newinstr;


				// update the label in the predecessors to reflect the preheader of the loop
				for( predecessor_block = successor_block->predecessor; predecessor_block; predecessor_block = predecessor_block->next) {
					if(predecessor_block->block == current_block || predecessor_block->block->number > successor_block->number )
						continue;
					switch(simple_op_format(predecessor_block->block->end->instr->opcode)) {
						case BJ_FORM: {
							if(predecessor_block->block->end->instr->u.bj.target == current_successor->block->start->instr->u.label.lab)	
								predecessor_block->block->end->instr->u.bj.target = insert_instr->u.label.lab;
							break;
						}
						case MBR_FORM: {
							if(predecessor_block->block->end->instr->u.mbr.deflab == current_successor->block->start->instr->u.label.lab)
								predecessor_block->block->end->instr->u.mbr.deflab = insert_instr->u.label.lab;
							else {
								int itarget = 0;
								for(; itarget < predecessor_block->block->end->instr->u.mbr.ntargets; itarget++) {
									if(predecessor_block->block->end->instr->u.mbr.targets[itarget] == current_successor->block->start->instr->u.label.lab)
									{
										predecessor_block->block->end->instr->u.mbr.targets[itarget] = insert_instr->u.label.lab;
									}
								}
							}
							break;
						}
					}
				}
			}
		}
	}
}

// test function to print the block_ptr
void print_block_ptr(block_ptr *head) {
	block_ptr * current_block = head;

	while(current_block) {
		printf("block number = %d & next-> %x\n", current_block->block->number, current_block->next);
		current_block = current_block->next;
	}
}

// insert a block_ptr, so that it is sorted. 
void insert_block_ptr(block_ptr ** head, basic_block_node * newblock) {
	block_ptr * current = NULL;
	block_ptr * previous = NULL;
	block_ptr * newnode = (block_ptr *) malloc(sizeof(block_ptr));
	newnode->block = newblock;
	newnode->next = NULL;

	if(*head == NULL) 
		*head = newnode;
	else if((*head)->block->number > newnode->block->number) {
		newnode->next = *head;
		*head = newnode;
	}
	else {		
		for(current = *head, previous = *head; current; previous = current, current = current->next) {
			if(current->block->number > newnode->block->number) {
				break;
			}
		}

		newnode->next = current;
		previous->next = newnode;
	}
}

// insert a loop block sorted into the list.
void insert_loop_block(loop_block ** head, loop_block * newnode) {
	loop_block * current = NULL;
	loop_block * previous = NULL;

	if(*head == NULL)
		*head = newnode;
	else if((*head)->head->block->number > newnode->head->block->number) {
		newnode->next = *head;
		*head = newnode;
	} else {
		for(current = *head, previous = *head; current; previous = current, current = current->next) {
			if(current->head->block->number > newnode->head->block->number)
				break;
		}
		newnode->next = current;
		previous->next = newnode;
	}
}

// find a loop block based on the header
loop_block * find_same_header(loop_block * loop_head, basic_block_node * successor) {
	loop_block * current_loop = NULL;

	for( current_loop = loop_head; current_loop; current_loop = current_loop->next)
	{
		if(current_loop->head->block->number == successor->number)
			return current_loop;
	}

	return current_loop;
}

// implements the push function of the stack
void insert_on_stack(block_ptr ** stack, basic_block_node * node) {
	block_ptr * newnode = (block_ptr*) malloc(sizeof(block_ptr));
	newnode->block = node;

	newnode->next = *stack;
	*stack = newnode;
}

// implements the pop function of the stack
block_ptr * pop(block_ptr ** stack) {
	block_ptr * temp = NULL;
	if(*stack != NULL) {
		temp = *stack;
		*stack = (*stack)->next;
	}

	return temp;
}

// finds loop info
//  - such as head, tails & nodes
int find_loop_info(basic_block_node * cfg, loop_block ** loop_head, int max_block_number) {
	basic_block_node * current_block = NULL;
	loop_block * currentloop = NULL;
	block_ptr * current_successor = NULL;
	int loop_count = 0;
	
	for( current_block = cfg; current_block; current_block = current_block->next) {
		for( current_successor = current_block->successor; current_successor; current_successor = current_successor->next) {
			if(current_successor->block->number <= current_block->number && get_bit(current_block->dom, current_successor->block->number)) {
				loop_block * newloop = NULL;
				
				newloop = find_same_header( *loop_head, current_successor->block );

				if(newloop) {
					insert_block_ptr(&(newloop->tail), current_block);
				} else {
					block_ptr * tail = NULL;
					newloop = (loop_block *) malloc(sizeof(loop_block));
					newloop->head = NULL;
					newloop->tail = NULL;
					newloop->next = NULL;
					insert_block_ptr(&(newloop->head), current_successor->block);
					insert_block_ptr(&(newloop->tail), current_block);
					insert_loop_block(loop_head, newloop);
				}
			}
		}
	}

// for each loop, find the nodes 

	currentloop = *loop_head;
	while(currentloop) {
		block_ptr * stack = NULL;
		block_ptr * tail = currentloop->tail;
		currentloop->nodes = new_bit_vector(max_block_number);
		set_all_bits(currentloop->nodes, FALSE);
		set_bit(currentloop->nodes, currentloop->head->block->number, TRUE);
		if(tail->block == currentloop->head->block) {
			currentloop = currentloop->next;
			continue;
		}
		for(; tail; tail = tail->next) {
        	set_bit(currentloop->nodes, tail->block->number , TRUE);
        	insert_on_stack(&stack, tail->block);
		}

        while(stack) {
        	block_ptr * m = pop(&stack);
            block_ptr * predecessor = m->block->predecessor;
            for( ; predecessor; predecessor = predecessor->next) {
            	if(!get_bit(currentloop->nodes, predecessor->block->number)) {
                	set_bit(currentloop->nodes, predecessor->block->number, TRUE);
                    insert_on_stack(&stack, predecessor->block);
                }
            }
    	}
		currentloop = currentloop->next;
		loop_count++;
	}

	return loop_count;
}